package com.lsa.letcode.the63.uniquePath2;

import java.util.LinkedList;
import java.util.Queue;

public class Solution {
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int m = obstacleGrid.length;
		int n = obstacleGrid[0].length;
		
		int[][] cells = new int[m][n];
		Queue<Coords> q = new LinkedList<Coords>();
		if (obstacleGrid[0][0] == 0 ) {
			cells[0][0] = 1;
			q.add(new Coords(0,0));
		}
		
		while(!q.isEmpty()) {
			Coords c = q.poll();
			int x = c.x;
			int y = c.y;
			
			if (x != m - 1 || y != n - 1) {
				if (x < m - 1 && obstacleGrid[x + 1][y] == 0) {
					if (cells[x + 1][y] == 0) {
						q.add(new Coords(x + 1, y));
					}
					
					cells[x + 1][y] += cells[x][y];
				}
				
				if (y < n - 1 && obstacleGrid[x][y + 1] == 0) {
					if (cells[x][y + 1] == 0) {
						q.add(new Coords(x, y + 1));
					}
					
					cells[x][y + 1] += cells[x][y];
				}
			}
		}
		
		return cells[m - 1][n - 1];
	}
	
	private class Coords {
		int x;
		int y;
		
		public Coords(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}
}